package ru.kpm.rectpack.utils;

import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * Класс предназначенный для оптимизации раскроя/загрузки прямоугольной области на
 * одинаковые прямоугольники
 *
 */
public class RectPacking
{


		public static void main(String[] args)
	{
		System.out.println("Hello World!");
		RectPacking a=new RectPacking();
		//List<Rectangle> l=a.optimize(240,1200,0,0,68,86);
		//List<Rectangle> l=a.optimize(5,5,0,0,2,3);
		System.out.println(new RectPacking().mxDiv(2310,860,680));
		//List<Rectangle> l=a.optimize(5950,2320,50,50,860,680);
		List<Rectangle> l=a.optimize(400,300,0,0,310,220);
		for(Rectangle r:l)
			System.out.println("x="+r.getX()+" y="+r.getY()+" w="+r.getWidth()+" h="+r.getHeight());
    System.out.println(""+l.size());
	}
	public static List<Rectangle> optimize(int cx,int cy,int dcx,int dcy,int bx,int by)
	{
		List<Rectangle> res=new ArrayList();
		List<Rectangle> res1;
		RectPacking rp;
		rp=new RectPacking();
		res1=rp.packingOptimize(cx, cy, dcx, dcy, bx, by);
		if(rp.iter<=rp.gard)
			return res1;
		if(res1.size()>res.size())
			res=res1;
		rp=new RectPacking();
		res1=rp.packingOptimize(cy, cx, dcy, dcx, bx, by);
		if(rp.iter<=rp.gard)
			return res1;
		if(res1.size()>res.size())
			res=res1;
		rp=new RectPacking();
		res1=rp.packingOptimize(cx, cy, dcx, dcy, by, bx);
		if(rp.iter<=rp.gard)
			return res1;
		if(res1.size()>res.size())
			res=res1;
		rp=new RectPacking();
		res1=rp.packingOptimize(cy, cx, dcy, dcx, by, bx);
		if(rp.iter<=rp.gard)
			return res1;
		if(res1.size()>res.size())
			res=res1;
		return res;
		//return new RectPacking().packingOptimize(cx, cy, dcx, dcy, bx, by);
	}
/**
 * Оптимизация раскроя/упаковки проямоугольного контейнера на прямоугольные области
 * @param cx ширина контейнера
 * @param cy длина контейнера
 * @param dcx отступ слева и справа
 * @param dcy отступ спереди и сзадаи
 * @param bx ширина выкраиваемой области (коробки)
 * @param by длина выкраиваемой области (коробки)
 * @return список координак каждого прямоугольника (коробки)
 */
	private List<Rectangle> packingOptimize(int cx,int cy,int dcx,int dcy,int bx,int by)
	{

		x=cx-2*dcx;
		y=cy-2*dcy;
		//x=mxDiv(x,bx,by);
		//y=mxDiv(y,bx,by);
		this.bx=bx;
		this.by=by;
		this.bxy=bx*by;
		this.tail=x*y;
		mx=bx>by?bx:by;
		step(0,0);
		levels=null;
		shifts=null;
		tmpres=null;
		for(Rectangle r:result)
		{
			r.setLocation(r.getLocation().x+dcx, r.getLocation().y+dcy);
		}
		System.out.println("iter="+iter);
		return result;
	}
private int mxDiv(int l,int x,int y)
{
	int q=(l/x)*x;
	int mx=q+((l-q)/y)*y;
	System.out.println(q/x+"-"+(mx-q)/y);
	while(q>=0)
	{
		q-=x;
		if(((l-q)/y)*y+q>mx)
		{
			mx=((l-q)/y)*y+q;
			System.out.println(q/x+"-"+(mx-q)/y);
		}
	}
	return mx;

}
	private LinkedList<Integer> levels=new LinkedList<Integer>();
	private Map<Integer,Integer> shifts=new TreeMap();
	private List<Rectangle> result=new ArrayList<Rectangle>();
	private ArrayList<Rectangle> tmpres=new ArrayList();
	private int x;
	private int y;
	private int bx;
	private int by;
	private int mx;
	private int bxy;
	private int tail;
	private long iter=0;
	private long gard=10000000;

	private void step(int level,int shift)
	{

		if(tail<bxy||iter>gard)
			return;
		iter++;
		boolean b=false;
		for(int i=0;i<2;i++)
		{
			Rectangle r;
			if(i==0)
			{
				r=new Rectangle(shift,level,bx,by);
			}else
			{
				r=new Rectangle(shift,level,by,bx);
			}
			if(!isIntersect(r))
			{
				b=true;
				tmpres.add(r);
				if(tmpres.size()>result.size())
				{
					result=new ArrayList(tmpres);
					tail=x*y-bxy*result.size();
				}
				Integer l=(r.y+r.height);
				Iterator<Integer> it=levels.iterator();
				Integer z=null;
				int n=0;
				while(it.hasNext()&&(z=it.next()).intValue()<l)
					n++;
				if(z==null||z<l)
				{
					levels.add(l);
				}else if(!z.equals(l))
				{
					levels.add(n,l);
				}
				shifts.put(shift+r.width,shift+r.width);
				step(level,shift+r.width);
				if(z!=null&&!z.equals(l))
				{
					levels.remove(l);
				}
				tmpres.remove(tmpres.size()-1);
			}
		}


		Iterator<Integer> it=shifts.keySet().iterator();
		Integer z=null;
		while(it.hasNext()&&(z=it.next()).intValue()<shift);
		if(z!=null&&z.intValue()>shift)
			step(level,z);
		//переходим к новому уровню
		if((z!=null&&z.intValue()<shift)||levels.isEmpty())
			return;
		Integer lev=levels.removeFirst();

		int t=lev.intValue()*x-tmpres.size()*bxy;
		int lv=lev.intValue();
		Rectangle r;
		for(int i=tmpres.size()-1;i>=0&&(r=tmpres.get(i)).y+mx>lv;i--)
		{
			if(r.y+r.height>lv)
				t+=(r.y+r.height-lv)*r.width;

		}
		if(t<tail)
			step(lev,0);
		levels.addFirst(lev);
	}

	private int getDiffs(int lv)
	{
		int t=0;

		return t;
	}
	/**
	 * Проверка не пересекает ли уже имеющиеся примоугольники
	 * @param rect проверяемы прямоугольник
	 * @return true - пересекается; false- не пересекается
	 */
	private boolean isIntersect(Rectangle r1)
	{
		if(r1.x+r1.width>x||r1.height+r1.y>y)
			return true;
		Rectangle r2;
		for(int i=tmpres.size()-1;i>=0&&(r2=tmpres.get(i)).y+mx>r1.y;i--)
		{
			if(!(r1.x>=r2.x+r2.width||r2.x>=r1.x+r1.width||r1.y>=r2.y+r2.height||r2.y>=r1.y+r1.height))
			{
				return true;
			}
		}
		return false;
	}
}